Теорема Бернштейна-Кантора

Биекция между множествами $A$ и $B$ существует тогда и только тогда, когда существуют инъекции из $A$ в $B$ и из $B$ в $A$.

$\Large\implies$ Необходимость очевидна, так как биекция — частный случай инъекции. $\Large\impliedby$ Пусть $f: A \to B$ и $g: B \to A$ — инъекции. Обозначим $A_1 = g(B)$, $A_2 = g(f(A))$. Свойства функций: 1. $g$ — биекция $B$ на $A_1$. 2. $\phi = f \circ g$ — биекция $A$ на $A_2$ Так как $B$ равномощно $A_1$, достаточно построить биекцию $A$ на $A_1$. **Построение $\psi\mathpunct{:}~ A \to A_1$:** Положим: $$C_0 = A_1 \setminus A_2, \quad\quad C_n = \phi(C_{n-1}) ~~\forall{n \in \mathbb{N}}$$ $$C = \bigcup\limits_{n=0}^{\infty} C_i$$ Определим функцию $\psi: A \to A_1$ условием: $$\psi(a) = \begin{cases} a, & a \in C \\ \phi(a), & a \notin C \end{cases}$$ **Доказательство того, что $\psi$ — биекция $A$ на $A_1$:** $\psi(A) \subseteq A_1$ по построению $A_2$, $\phi$ и $C$. Докажем, что $\psi$ — биекция $A$ на $A_1$. Достаточно доказать, что любой элемент $c \in A_1$ имеет единственный $\psi$-прообраз. **Пусть $c \in C$:** $c$ — единственный $\psi$-прообраз $c$, принадлежащий $C$. Рассмотрим, может ли $a \in A \setminus C$ быть $\psi$-прообразом $c$: $$\text{если } a \in A \setminus C \text{ — } \psi\text{-прообраз } c \Rightarrow a = \phi^{-1}(c) \in C_i,~~ i \geq 1$$ $$\Rightarrow a \in C_{i-1} \text{ (противоречие, т.к. } a \notin C) \Rightarrow c \text{ — единственный } \psi\text{-прообраз } c$$ **Пусть $c \in A_1 \setminus C$:** У него нет $\psi$-прообразов в $C$. $c \in A_2$, т.е. имеет $\psi$-прообраз $\phi^{-1}(c)$ (единственный ввиду инъективности $\phi$). (Поскольку $c \notin C$, то $a = \phi^{-1}(c)$ также не может принадлежать $C$, иначе $c \in \phi(C) \subset C$). Таким образом, $\psi$ является биекцией $A$ на $A_1$. Так как $A_1$ равномощно $B$, то $A$ равномощно $B$. $\square$